package test7;

import java.util.LinkedList;
import java.util.List;

public class Demo2 {
    public static void main(String[] args) {
        TreeNode root = new TreeNode(1);
        root.left = new TreeNode(2);
        root.left.right = new TreeNode(3);
        root.right = new TreeNode(2);
        root.right.left = new TreeNode(3);
        //candidates = [2,3,6,7], target = 7
        int[] candidates = {2, 3, 6, 7};
        List<List<Integer>> lists = new Demo2().combinationSum(candidates, 7);
    }

    LinkedList<Integer> track = new LinkedList<>();
    List<List<Integer>> res = new LinkedList<>();

    public List<List<Integer>> combinationSum(int[] candidates, int target) {
        int min = Integer.MAX_VALUE;
        for (int i = 0; i < candidates.length; i++) {
            if (candidates[i] == 0) return null;
            if (min > Math.abs(candidates[i])) {
                min = Math.abs(candidates[i]);
            }
        }
        traverse(candidates, target, target / min);
        return res;
    }

    void traverse(int[] candidates, int target, int len) {
        if (track.size() > len) {
            return;
        }
        int sum = 0;
        for (Integer e : track) {
            sum += e;
        }
        if (sum == target) {
            System.out.println(track);
        }
        for (int i = 0; i < candidates.length; i++) {

            track.addLast(candidates[i]);
            traverse(candidates, target, len);
            track.removeLast();
        }
    }
}
